#include <bits/stdc++.h>

using namespace std;

using ll = long long;

// 极限数字

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll LNINF = 0xc0c0c0c0c0c0c0c0;

// 高精度计算

// 高精度根号
ll isqrt(ll N)
{
    ll sqrtN = sqrt(N) - 1;
    while (sqrtN + 1 <= N / (sqrtN + 1))
        sqrtN++;
    return sqrtN;
}

// 顶函数和底函数
ll fdiv(ll a, ll b)
{
    return a / b - ((a ^ b) < 0 && a % b);
}
ll cdiv(ll a, ll b)
{
    return a / b + ((a ^ b) > 0 && a % b);
}